The present invention relates generally to computational systems and methods, and more particularly, to a system and method for obtaining minimum and maximum values from a set of sample parameter values using a table of last occurrence and a sliding window. The present invention is particularly useful in systems that manage information transfers over a network through use of a cell prioritization scheme.
In many systems which routinely perform computations on a set of discrete variables or parameter values, it is often necessary to compute the minimum and maximum values from the set of parameter values. A traditional approach involves storing all of the parameter values in a memory, sorting the parameter values, and then obtaining the minimum and maximum values from the sorted list of values. In a system in which new data is added on a continuous basis, this traditional approach becomes very time consuming and potentially very costly in terms of memory resources and computing overhead.
In the communications industry, for example, certain systems are required to perform minimum and/or maximum determinations on a repetitive basis and at a relatively high speed. For example, one particular communications technology, referred to as asynchronous transfer mode (ATM), typically utilizes a number of switches or nodes to facilitate the rapid transfer of information cells between source and destination end-stations. Various schemes have been developed to discriminate between cells which are to be accepted by a particular node and cells which are to be discarded by the node. It may be desirable to prioritize cells received by a node using a rating scheme that assigns a priority identifier to each cell, such that the priority identifier indicates the importance of the cell relative to other cells received by the node. It would further appear desirable to implement an information collecting strategy at the node that exploits a high speed, low-overhead minimum and/or maximum priority identifier determination procedure.
There is a need for an improved approach to determining the minimum and/or maximum values from a set of values which increases in size over time, and a need for an approach which requires reduced memory requirements and processing overhead. There is an additional need for such an approach which can be exploited in high-speed ATM switches. The present invention fulfills these and other needs.
The present invention is directed to a system and method for determining the minimum and/or maximum values from a number of sample parameter values. A table of last occurrence (TOLO-table) is employed, together with a sliding window or filter, to greatly enhance the speed and efficiency when determining the minimum and/or maximum value from a number of sample parameter values that fall within the sliding window. The values of the sample parameters processed using the TOLO-table are typically discrete in nature and restricted to N number of different possible values (e.g., pi=p1, p2, . . . pN).
A TOLO-table typically includes a parameter column for storing entries for each one of a limited number of discrete parameter values, such as integers or alphabetic letters, for example. The TOLO-table also includes a time stamp column which provides entries for storing time of receipt data associated with each of the parameter values defined in the parameter column. Alternatively, an order number column, rather than a time stamp column, may be employed for storing number order entries corresponding to the order in which the parameter values occur or are received. Every time a parameter value is received, the time stamp or order number entry associated with the parameter value is updated to the current time or order number. The most recent or last occurrence of a particular parameter value is thus recorded in the TOLO-table.
The minimum and/or maximum values of a set of parameter values maintained in the TOLO-table may be obtained using a sliding window which may be adjusted in size or duration. The sliding window may be defined on the basis of time or by a selected number of sample parameter values. The parameter values falling within the sliding window are scanned to determine the minimum and/or maximum of the applicable parameter values. The TOLO-table also provides an accurate basis for determining whether there has been at least one occurrence of a particular parameter value within the sliding window, in addition to the minimum and/or maximum parameter values.
A minimum/maximum determination methodology that employs a TOLO-table and sliding window in accordance with the principles of the present invention may be used in a wide variety of applications, and is particularly useful in ATM network applications. In one embodiment of an ATM service model, each cell of information is assigned a priority value which determines, in part, the importance of the cell relative to other cells being transmitted through the network. A network node accepts or discards a newly arriving cell based on the priority level of the cell and a threshold priority level computed by the node. If requested, the network node may inform the source about a typical threshold priority level that has been computed in the node. One possible implementation for determining this typical threshold priority level includes the determination of the highest priority level among a set of computed threshold priority levels. A TOLO-table may be used for determining this information.